package com.gxar.navigation.server.base.common.utils;

import com.gxar.navigation.server.base.common.constant.RedisKeyConstant;
import com.gxar.navigation.server.base.model.arithmetic.dto.Maps;

import java.util.*;
import java.util.Map.Entry;

/**
 * Dijkstra 图最短路径搜索算法
 *
 * @param <T> 节点的主键类型
 * @author Linsy
 * @date 2023-09-15
 */
public class MapSearcher<T> {

    /**
     * 地图对象
     */
    private Maps<T> map;
    /**
     * 开始节点
     */
    private Maps.Node<T> startNode;
    /**
     * 结束节点
     */
    private Maps.Node<T> targetNode;
    /**
     * 开放的节点
     */
    private final Set<Maps.Node<T>> open = new HashSet<>();
    /**
     * 关闭的节点
     */
    private final Set<Maps.Node<T>> close = new HashSet<>();
    /**
     * 最短路径距离
     */
    private final Map<Maps.Node<T>, Long> path = new HashMap<>();
    /**
     * 最短路径
     */
    private final Map<T, List<T>> pathInfo = new HashMap<>();

    /**
     * 最短路径搜索结果类
     *
     * @param <T> 节点的主键类型
     */
    public static class SearchResult<T> {
        /**
         * 最短路径结果
         */
        List<T> path;
        /**
         * 最短距离
         */
        Long distance;

        /**
         * 获取实例
         *
         * @param path     最短路径结果
         * @param distance 最短路径距离
         * @return 结果
         */
        protected static <T> SearchResult<T> valueOf(List<T> path, Long distance) {
            SearchResult<T> r = new SearchResult<T>();
            r.path = path;
            r.distance = distance;
            return r;
        }

        /**
         * 获取路径
         *
         * @return 路径
         */
        public List<T> getPath() {
            return path;
        }

        /**
         * 获取权重
         *
         * @return 权重
         */
        public Long getDistance() {
            return distance;
        }

        @Override
        public String toString() {
            StringBuffer sb = new StringBuffer();
            sb.append("path:");
            for (Iterator<T> it = this.path.iterator(); it.hasNext(); ) {
                sb.append(it.next());
                if (it.hasNext()) {
                    sb.append("->");
                }
            }
            sb.append("\n").append("distance:").append(distance);
            return sb.toString();
        }

    }

    /**
     * 初始化起始点
     * <br/>初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离"
     * [例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。
     *
     * @param source   起始节点的Id
     * @param map      全局地图
     * @param closeSet 已经关闭的节点列表
     */
    public void init(T source, Maps<T> map, Set<T> closeSet) {

        Map<T, Maps.Node<T>> nodeMap = map.getNodes();
        Maps.Node<T> startNode = nodeMap.get(source);
        //将初始节点放到close
        close.add(startNode);
        //将其他节点放到open
        for (Maps.Node<T> node : nodeMap.values()) {
            if (!closeSet.contains(node.getId()) && !node.getId().equals(source)) {
                this.open.add(node);
            }
        }

        // 初始路径
        T startNodeId = startNode.getId();
        for (Entry<Maps.Node<T>, Long> entry : startNode.getChild().entrySet()) {
            Maps.Node<T> node = entry.getKey();
            if (open.contains(node)) {
                T nodeId = node.getId();
                path.put(node, entry.getValue());
                pathInfo.put(nodeId, new ArrayList<T>(Arrays.asList(startNodeId, nodeId)));
            }
        }

        for (Maps.Node<T> node : nodeMap.values()) {
            if (open.contains(node) && !path.containsKey(node)) {
                path.put(node, Long.MAX_VALUE);
                pathInfo.put(node.getId(), new ArrayList<T>(Collections.singletonList(startNodeId)));
            }
        }
        this.startNode = startNode;
        this.map = map;
    }


    /**
     * 递归Dijkstra
     *
     * @param start 已经选取的最近节点
     */
    protected void computePath(Maps.Node<T> start) {
        // 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。
        Maps.Node<T> nearest = getShortestPath(start);
        if (nearest == null) {
            return;
        }
        //更新U中各个顶点到起点s的距离。
        //之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；
        //例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。
        close.add(nearest);
        open.remove(nearest);
        //已经找到结果
        if (nearest == this.targetNode) {
            return;
        }
        Map<Maps.Node<T>, Long> childs = nearest.getChild();
        for (Maps.Node<T> child : childs.keySet()) {
            if (open.contains(child)) {// 如果子节点在open中
                Long newCompute = path.get(nearest) + childs.get(child);
                if (path.get(child) > newCompute) {// 之前设置的距离大于新计算出来的距离
                    path.put(child, newCompute);

                    List<T> path = new ArrayList<T>(pathInfo.get(nearest.getId()));
                    path.add(child.getId());
                    pathInfo.put(child.getId(), path);
                }
            }
        }
        // 向外一层层递归,直至所有顶点被遍历
        computePath(nearest);
    }

    /**
     * 获取与node最近的子节点
     *
     * @param node node
     * @return 子节点
     */
    private Maps.Node<T> getShortestPath(Maps.Node<T> node) {
        Maps.Node<T> res = null;
        Long minDis = Long.MAX_VALUE;
        for (Maps.Node<T> entry : path.keySet()) {
            if (open.contains(entry)) {
                Long distance = path.get(entry);
                if (distance < minDis) {
                    minDis = distance;
                    res = entry;
                }
            }
        }
        return res;
    }

    /**
     * 获取到目标点的最短路径
     *
     * @param target 目标点
     * @return 最短路径
     */
    public SearchResult<T> getResult(T target) {
        Maps.Node<T> targetNode = this.map.getNodes().get(target);
        if (targetNode == null) {
            throw new RuntimeException("目标节点不存在!");
        }
        this.targetNode = targetNode;
        //开始计算
        this.computePath(startNode);
        return SearchResult.valueOf(pathInfo.get(target), path.get(targetNode));
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {

        Maps.MapBuilder<Long> mapBuilder = new Maps.MapBuilder<Long>().create();
        //构建节点
        mapBuilder.addNode(Maps.Node.valueOf(1L));
        mapBuilder.addNode(Maps.Node.valueOf(2L));
        mapBuilder.addNode(Maps.Node.valueOf(3L));
        mapBuilder.addNode(Maps.Node.valueOf(4L));
        mapBuilder.addNode(Maps.Node.valueOf(5L));
        mapBuilder.addNode(Maps.Node.valueOf(6L));
        mapBuilder.addNode(Maps.Node.valueOf(7L));
        mapBuilder.addNode(Maps.Node.valueOf(8L));
        mapBuilder.addNode(Maps.Node.valueOf(9L));
        //构建路径
        mapBuilder.addPath(1L, 2L, 1);
        mapBuilder.addPath(1L, 6L, 2);
        mapBuilder.addPath(1L, 4L, 4);
        mapBuilder.addPath(1L, 3L, 1);
        mapBuilder.addPath(1L, 7L, 5);
        mapBuilder.addPath(3L, 7L, 3);
        mapBuilder.addPath(7L, 8L, 1);
        mapBuilder.addPath(8L, 2L, 4);
        mapBuilder.addPath(2L, 6L, 2);
        mapBuilder.addPath(5L, 6L, 1);
        mapBuilder.addPath(4L, 5L, 1);
        mapBuilder.addPath(8L, 9L, 1);
        mapBuilder.addPath(3L, 9L, 1);

        //构建全局Map
        Maps<Long> map = mapBuilder.build();

        //创建路径搜索器(每次搜索都需要创建新的MapSearcher)
        MapSearcher<Long> searcher = new MapSearcher<>();
        //创建关闭节点集合
        Set<Long> closeNodeIdsSet = new HashSet<Long>();
//        closeNodeIdsSet.add(3L);
        //设置初始节点
        searcher.init(1L, map, closeNodeIdsSet);
        //获取结果
        SearchResult<Long> result = searcher.getResult(9L);
        List<Long> resultPath = result.getPath();
        for (int i = 0; i < resultPath.size() - 1; i++) {
            System.out.println(resultPath.get(i) + " -> " + resultPath.get(i + 1));
        }
        System.out.println(result);

        String formatted = String.format(RedisKeyConstant.GRAPH_NODE_KEY, 1L, 2L);
        System.out.println(formatted);
    }

}